package binaryTree.LayerOrderTraversal;

import java.util.*;

//1月5日
class  TreeNode{
    public TreeNode left;
    public TreeNode right;
    public  int val;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class VariousBianLi{

    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        preOrderTraver(root,list);
        return  list;
    }

//递归实现遍历
    public  void preOrderTraver(TreeNode root, ArrayList list){
        if (root==null){
            return;
        }
        preOrderTraver(root.left,list);
        list.add(root.val);
        preOrderTraver(root.right,list);
    }

//    非递归实现遍历
//  先序遍历
    public   List<Integer>  preOrder( TreeNode  root){
        ArrayList<Integer> result= new ArrayList<>();
        if (root==null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right!=null){
                stack.push(node.right);
            }
            if (node.left!=null){
                stack.push(node.left);
            }
        }
        return  result;
    }
//后序遍历
    public   List<Integer>  postOrder( TreeNode  root){

        ArrayList<Integer> result= new ArrayList<>();

        if (root==null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left!=null){
                stack.push(node.left);
            }
            if (node.right!=null){
                stack.push(node.right);
            }
        }
//对List进行转置
        Collections.reverse(result);
        return  result;
    }

//    中序遍历
    public   List<Integer>  inOrder( TreeNode  root){
        ArrayList<Integer> result= new ArrayList<>();
        if (root==null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur=root; //cur类似C里面得指针  指向遍历过的节点   stack来进行存储
        while (cur!=null || !stack.isEmpty()){
            if (cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            //上面一路向左遍历  遇  到空的了 就要开始处理 也就是加入到list中
            else {
               cur= stack.pop();
                result.add(cur.val);
                cur=cur.right;
            }
        }
        return  result;
    }

    //层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> resList = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root!=null){
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> temp = new ArrayList<>();
            while (size>0){
                TreeNode node = queue.poll();
                size--;
                temp.add(node.val);
                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
            }
            resList.add(temp);
        }
        return  resList;
    }



    public List<List<Integer>> levelOrderBottom(TreeNode root) {
//        二叉树的层序遍历，就是最后把result数组反转一下就可以了
        List<List<Integer>> resList = new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root!=null){
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> temp = new ArrayList<>();
            while (size>0){
                TreeNode node = queue.poll();
                size--;
                temp.add(node.val);

                if (node.left!=null){
                    queue.offer(node.left);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                }
            }
            resList.add(temp);
        }

        Collections.reverse(resList);
        return resList;
    }


    //同一版本　迭代实现前中后序遍历　　
    //todo:无论是前中后序遍历　添加的顺序都是　都是与原本遍历顺序倒着进行添加　
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }



    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }


    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }



    public static void main(String[] args) {
     TreeNode root= new TreeNode(5);
       TreeNode treeNode1 = new  TreeNode(3);
      TreeNode treeNode2=new TreeNode(1);
       TreeNode treeNode3 = new TreeNode(2);
       TreeNode treeNode4= new TreeNode(6);
        root.left=treeNode1;
        root.right=treeNode3;
        treeNode1.left=treeNode2;
        treeNode3.right=treeNode4;

//        Basic144 basic144 = new Basic144();
//        List<Integer> integers = basic144.preorderTraversal(root);
//        for (int a :integers
//             ) {
//            System.out.println(a);
//        }
//
        }





//
//        List<List<Integer>> list= basic144.levelOrderBottom(root);
//
//
//
//        for (List<Integer>  a:  list
//             ) {
//            for (int  b: a
//                 ) {
//                System.out.println(b);
//            }
//        }
//    }

}
